
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">


<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>Bitsets &mdash; LLVM 3.7 documentation</title>
    
    <link rel="stylesheet" href="_static/llvm-theme.css" type="text/css" />
    <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    './',
        VERSION:     '3.7',
        COLLAPSE_INDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="_static/jquery.js"></script>
    <script type="text/javascript" src="_static/underscore.js"></script>
    <script type="text/javascript" src="_static/doctools.js"></script>
    <link rel="top" title="LLVM 3.7 documentation" href="index.html" />
    <link rel="next" title="FaultMaps and implicit checks" href="FaultMaps.html" />
    <link rel="prev" title="MergeFunctions pass, how it works" href="MergeFunctions.html" />
<style type="text/css">
  table.right { float: right; margin-left: 20px; }
  table.right td { border: 1px solid #ccc; }
</style>

  </head>
  <body role="document">
<div class="logo">
  <a href="index.html">
    <img src="_static/logo.png"
         alt="LLVM Logo" width="250" height="88"/></a>
</div>

    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             accesskey="I">index</a></li>
        <li class="right" >
          <a href="FaultMaps.html" title="FaultMaps and implicit checks"
             accesskey="N">next</a> |</li>
        <li class="right" >
          <a href="MergeFunctions.html" title="MergeFunctions pass, how it works"
             accesskey="P">previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="index.html">Documentation</a>&raquo;</li>
 
      </ul>
    </div>


    <div class="document">
      <div class="documentwrapper">
          <div class="body" role="main">
            
  <div class="section" id="bitsets">
<h1>Bitsets<a class="headerlink" href="#bitsets" title="Permalink to this headline">¶</a></h1>
<p>This is a mechanism that allows IR modules to co-operatively build pointer
sets corresponding to addresses within a given set of globals. One example
of a use case for this is to allow a C++ program to efficiently verify (at
each call site) that a vtable pointer is in the set of valid vtable pointers
for the type of the class or its derived classes.</p>
<p>To use the mechanism, a client creates a global metadata node named
<code class="docutils literal"><span class="pre">llvm.bitsets</span></code>.  Each element is a metadata node with three elements:
the first is a metadata string containing an identifier for the bitset,
the second is a global variable and the third is a byte offset into the
global variable.</p>
<p>This will cause a link-time optimization pass to generate bitsets from the
memory addresses referenced from the elements of the bitset metadata. The pass
will lay out the referenced globals consecutively, so their definitions must
be available at LTO time. The <a class="reference external" href="http://llvm.org/klaus/llvm/blob/master/include/llvm/Transforms/IPO/LowerBitSets.h">GlobalLayoutBuilder</a> class is responsible for
laying out the globals efficiently to minimize the sizes of the underlying
bitsets. An intrinsic, <a class="reference internal" href="LangRef.html#bitset-test"><span>llvm.bitset.test</span></a>, generates code
to test whether a given pointer is a member of a bitset.</p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field-odd field"><th class="field-name">Example:</th><td class="field-body"></td>
</tr>
</tbody>
</table>
<div class="highlight-python"><div class="highlight"><pre>target datalayout = &quot;e-p:32:32&quot;

@a = internal global i32 0
@b = internal global i32 0
@c = internal global i32 0
@d = internal global [2 x i32] [i32 0, i32 0]

!llvm.bitsets = !{!0, !1, !2, !3, !4}

!0 = !{!&quot;bitset1&quot;, i32* @a, i32 0}
!1 = !{!&quot;bitset1&quot;, i32* @b, i32 0}
!2 = !{!&quot;bitset2&quot;, i32* @b, i32 0}
!3 = !{!&quot;bitset2&quot;, i32* @c, i32 0}
!4 = !{!&quot;bitset2&quot;, i32* @d, i32 4}

declare i1 @llvm.bitset.test(i8* %ptr, metadata %bitset) nounwind readnone

define i1 @foo(i32* %p) {
  %pi8 = bitcast i32* %p to i8*
  %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !&quot;bitset1&quot;)
  ret i1 %x
}

define i1 @bar(i32* %p) {
  %pi8 = bitcast i32* %p to i8*
  %x = call i1 @llvm.bitset.test(i8* %pi8, metadata !&quot;bitset2&quot;)
  ret i1 %x
}

define void @main() {
  %a1 = call i1 @foo(i32* @a) ; returns 1
  %b1 = call i1 @foo(i32* @b) ; returns 1
  %c1 = call i1 @foo(i32* @c) ; returns 0
  %a2 = call i1 @bar(i32* @a) ; returns 0
  %b2 = call i1 @bar(i32* @b) ; returns 1
  %c2 = call i1 @bar(i32* @c) ; returns 1
  %d02 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 0)) ; returns 0
  %d12 = call i1 @bar(i32* getelementptr ([2 x i32]* @d, i32 0, i32 1)) ; returns 1
  ret void
}
</pre></div>
</div>
</div>


          </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related" role="navigation" aria-label="related navigation">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="genindex.html" title="General Index"
             >index</a></li>
        <li class="right" >
          <a href="FaultMaps.html" title="FaultMaps and implicit checks"
             >next</a> |</li>
        <li class="right" >
          <a href="MergeFunctions.html" title="MergeFunctions pass, how it works"
             >previous</a> |</li>
  <li><a href="http://llvm.org/">LLVM Home</a>&nbsp;|&nbsp;</li>
  <li><a href="index.html">Documentation</a>&raquo;</li>
 
      </ul>
    </div>
    <div class="footer" role="contentinfo">
        &copy; Copyright 2003-2015, LLVM Project.
      Last updated on 2015-09-08.
      Created using <a href="http://sphinx-doc.org/">Sphinx</a> 1.3.1.
    </div>
  </body>
</html>